#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;
const LL MOD = 1e9;

LL f[N];
LL infix[N]; 

int main()
{
	int n, k; cin >> n >> k;
	for(int i = 0; i < k; i++) 
	{
		f[i] = 1;
		infix[i] = f[i];
		infix[i] += infix[i - 1];
	}
	for(int i = k; i <= n; i++)
	{
		f[i] = (infix[i - 1] - infix[i - k - 1]) % MOD;
		infix[i] = (f[i] + infix[i - 1]) % MOD;
	}	
//	for(int i = 0; i <= n; i++) cout << infix[i] << " ";
	cout << (f[n] + MOD) % MOD << endl;
	return 0;
} 
